package hot.huisu;

public class A79 {

}






/**
 * 未优化
 */

class Solution {
    int[][] vis;
    boolean flag=false;
    int[] d1={1,0,-1,0};
    int[] d2={0,1,0,-1};
    public boolean exist(char[][] board, String word) {
        int n=board.length;
        int m=board[0].length;
        this.vis=new int[n][m];
        char c=word.charAt(0);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]==c){
                    vis[i][j]=1;//已经遍历
                    dfs(1,i,j,word,board);
                    vis[i][j]=0;
                }
            }
        }
        return flag;
    }
    //i代表当前word要收集字母下标,i==word.length代表收集完毕,(a,b)代表当前所在字母下标，已经收集
    void dfs(int index,int a,int b, String word,char[][] board){
        if(index==word.length()){
            flag=true;
            return;
        }
        char cur=word.charAt(index);
        for(int i=0;i<4;i++){
            int x=a+d1[i];
            int y=b+d2[i];
            //范围内点，符合，没访问过
            if(x>=0&&x<board.length&&y>=0&&y<board[0].length&&board[x][y]==cur&&vis[x][y]==0){
                vis[x][y]=1;
                dfs(index+1,x,y,word,board);
                vis[x][y]=0;
            }
        }
    }
}